3.4 Let p be a permutation of the integers 0, 1, 2, ... (2n- 1) such that p(m) gives the permuted value of m, 0 ≠ m <= 2n. Put another way, p maps the set of n-bit integers into itself and no two integers map into the sameinteger. DES is such a permutation for 64-bit integers. We say that p has a fixed point at m if p(m) = m. Thatis, if p is an encryption mapping, then a fixed point corresponds to a message that encrypts to itself. We areinterested in the probability that p has no fixed points. Show the somewhat unexpected result that over 60% of mappings will have at least one fixed point. | |
| View Solution | |
| << Back | Next >> |